class Solution {
 public:
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   *
   * @param matrix char字符型vector<vector<>>
   * @param word string字符串
   * @return bool布尔型
   */
  // 回溯典型题目，回溯函数有返回值
  bool hasPath(vector<vector<char>>& matrix, string word) {
    // write code here
    int m = matrix.size();
    int n = matrix[0].size();
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (dfs(matrix, word, i, j, 0)) return true;
      }
    }
    return false;
  }
  bool dfs(vector<vector<char>>& matrix, string& word, int i, int j, int idx) {
    if (i >= matrix.size() || i < 0 || j >= matrix[0].size() || j < 0 ||
        matrix[i][j] != word[idx])
      return false;
    if (idx == word.size() - 1) return true;
    char tmp = matrix[i][j];
    matrix[i][j] = '.';
    bool res = dfs(matrix, word, i + 1, j, idx + 1) ||
               dfs(matrix, word, i - 1, j, idx + 1) ||
               dfs(matrix, word, i, j + 1, idx + 1) ||
               dfs(matrix, word, i, j - 1, idx + 1);
    matrix[i][j] = tmp;
    return res;
  }
};